原贴地址：[http://blog.leanote.com/post/dawnmagnet/74b9cba6cc8a](http://blog.
leanote.com/post/dawnmagnet/74b9cba6cc8a)
# 题目
![title](https://leanote.com/api/file/getImage?fileId=60a31386ab64411fb000251
e)
# 思路分析
又是一道异或的题目。
我们再强调一下，异或的最重要的性质就是**两个相同的数字异或是0**
接下来看一下我们的这个数据量，不太适合暴力，如果按照题目的说法对(i, j, 
k)三元组进行遍历，复杂度就是$O(n^3)$，达到了$300^3=27000000$复杂度，这种已经
很大了，很危险，很有可能过不了。这也是对于所有题目的一个小提示：如果复杂度达
到$10^9$，就过不了了。
这个题目既然如此危险，不到万不得已就不写暴力算法。
此处说明一下优化的手段，一般来说O(n^2)的算法只能往O(n)和O(nlgn)进行优化，但这
里我们观察了一下也没什么可以二分的办法，所以我们就用O(n)进行思考，既然是O(n)
那么每一次查询都应该是O(1)的复杂度，有可能吗？
这里就要介绍一下前缀和的思想。
我们先思考一个跟本问题很像的一个问题，就是我们将本题中的异或换成加法。我们给
入一个查询，查询的是数组中间某一段的和。为了在O(1)的时间应对每次查询，我们新
建一个前缀和数组，称为prefix
prefix中的下标|arr中的下标
--|--
0|n0
1|n0+n1
2|n0+n1+n2
3|n0+n1+n2+n3
4|n0+n1+n2+n3+n4
...|...
如果我们获得了前缀和数组，对于每次查询都能在O(1)的时间返回，因为如果我们想要
获得1至3之间的值（包含3），我们就用**prefix[3]-prefix[0]**就获得了1至3之间的
值的和。
我们再仔细思考一下为什么是加法就可以这么做。以及换成异或之后我们应该如何做。
性质|加法+|异或^
--|--
逆操作|减法-|异或^
一顺一逆的结果|0+n-n=0|0^n^n=0
现在我们可以知道为什么上述操作中我们会用**prefix[3]减去prefix[0]**，因为减法
是加法的逆操作。而正因为一顺一逆的结果是0，这个前缀和才有它存在的意义。
我们仿照着加法设计出来我们的异或前缀和表
prefix中的下标|arr中的下标
--|--
0|n0
1|n0^n1
2|n0^n1^n2
3|n0^n1^n2^n3
4|n0^n1^n2^n3^n4